// https://leetcode.cn/problems/substring-with-concatenation-of-all-words/description/

// 算法思路总结：
// 1. 滑动窗口解决串联所有单词的子串问题
// 2. 将每个单词视为一个字符单位，窗口大小为m×n
// 3. 按单词长度n进行分组，避免遗漏起始位置
// 4. 使用哈希表统计窗口内单词频次，与目标频次比较
// 5. 维护count变量记录有效单词数，达到m时记录结果
// 6. 时间复杂度：O(n×len)，空间复杂度：O(m)

#include <iostream>
using namespace std;

#include <vector>
#include <string>
#include <unordered_map>

class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words) 
    {
        int m = words.size(), n = words[0].size();
        unordered_map<string, int> hash2;
        vector<int> ret;

        for (const string& str : words)
        {
            hash2[str]++;
        }

        for (int i = 0 ; i < n ; i++)
        {
            unordered_map<string, int> hash1;
            
            for (int left = i, right = i, count = 0 ; right + n <= s.size() ; right += n)
            {
                string in = s.substr(right, n);
                hash1[in]++;

                if (hash1[in] <= hash2[in])
                {
                    count++;
                }

                if (right - left + 1 > m * n)
                {
                    string out = s.substr(left, n);
                    hash1[out]--;
                    left += n;
                    if (hash1[out] < hash2[out])
                    {
                        count--;
                    }
                }

                if (count == m)
                {
                    ret.push_back(left);
                }
            }
        }

        return ret;
    }
};

int main()
{
    string s1 = "barfoothefoobarman", s2 = "barfoofoobarthefoobarman";
    vector<string> words1 = {"foo","bar"}, words2 = {"bar","foo","the"};

    Solution sol;

    auto v1 = sol.findSubstring(s1, words1);
    auto v2 = sol.findSubstring(s2, words2);

    for (const int& num : v1)
        cout << num << " ";
    cout << endl;

    for (const int& num : v2)
        cout << num << " ";
    cout << endl;

    return 0;
}